package 字节笔试;

import java.util.Arrays;

/**
 @author fujiangnan
 @create 2021-11-12-15-42
 @desc ...
 */
public class Main2 {
    static int[][] dp;
    static int[] nums;
    public static void main(String[] args) {
        dp = new int[25][25];
        nums = new int[25];
        int a = 10;
        int b = 13;
        int res1 = getCnt(a);
        int res2 = getCnt(b);
        System.out.println(res2 - res1);

    }
    public static int dfs(int pos, int pre, boolean lead, boolean limit) {
        if (pos == 0) {
            return 0;
        }
        if(!lead && !limit && dp[pos][pre] !=-1) {
            return dp[pos][pre];
        }

        //如果position位置之前的所有数字都为它们位置的最大值,
        //那么当前位置最大只能够是读取的数字的当前位置的值
        //否则,这一位能够填写0~9,因为这种情况下不管怎么填写,数字都不会超过给定范围.
        int maxNum = limit?nums[pos]:9;
        int result = 0;
        int abs;
        for(int i = 0;i<=maxNum;i++) {
            abs = Math.abs(i - pre);
            //条件:相邻两个数字之间的差值必须不小于2,并且是没有前导零的情况
            //如果有前导零,那么就不需要这个条件.
            if (abs > 1 && !lead) {
                continue;
            }
            //当前位置取值不是0或者没有前导零
            //1.如果没有前导零,无论当前位取值如何,该状态表示的数字都不会是当前位置之前全部是零的情况
            //2.如果当前位置取值非零,那么之后一定不是前导零的状态了
            else if (i != 0 || !lead) {
                result += dfs(pos - 1, i, false, false);
            }
            //和上面的状态相反,这里就表示了,是前导零的状态.
            else {
                result += dfs(pos - 1, i, false, true);
            }
        }
        //这里针对一般的情况,进行了结果记录,以便后续使用
        //一般情况的条件:
        //1.各个位置不是最大取值
        //2.不包含前导零状态
        if(!limit && !lead){
            dp[pos][pre] = result;
        }
        return result;
    }

    private static int getCnt(int num){
        int index = 0;
        while (num>0){
            nums[index++] = num%10;
            num /= 10;
        }
        //将dp数组初始化为-1.因为后续需要记忆化搜索,通过初始化的-1,来表示,某个状态没有被记录到
        for(int i = 0;i<dp.length;i++){
            Arrays.fill(dp[i],-1);
        }
        return dfs(index-1,0,true,true);
    }
}
